DigitaI halftoning for the purpose of generating continuous-tone images has been practical since the mid-1960's (see "Picture Generation with a Standard Line Printer," by Perry and Mendelsohn, Comm. of the ACM, Vol. 7, No. 5, pp 311-313). The two major techniques in current use are dithering and error diffusion. See Digital Halftoning by Ulichney, MIT Press, Cambridge, Mass., pp 77-79, 127, 239-240. The prime dithering techniques are random dither, clustered-dot dither, and dispersed-dot dither. Random dither was developed first, but it is rarely used because it produces the poorest quality image.
The other two dither techniques are used with clustered-dot being by far the most prevalent. They are both based upon a threshold screen pattern that is generally a fixed size., e.g., 8.times.8 image pixels, which is compared with the input digital image values. If the input digital value is greater than the screen pattern number, the output is set "on", i.e., 255 for an 8-bit input image, and if it is less, the output is set to "off" or 0. The difference between the two techniques is the lower threshold values, which are centered in the clustered-dot screen pattern, but scattered in the dispersed-dot screen pattern. The clustered-dot technique has a central dot that increases in size as the signal level increases and the dispersed-dot technique has small scattered dots that increase in number as the signal level increases. In both techniques the number of levels that can be represented is equal to the size of the pixels of the screen pattern, e.g., an 8.times.8 screen can produce 64 unique levels.
Larger patterns allow more levels, but also a reduction in the effective resolution because the transition between levels is at a coarser pitch. At the medium pixel rate of copiers and laser printers, e.g., 300-500 dots/inch, the pattern artifacts are visible for screen patterns larger than 4.times.4, and since 16 levels are inadequate precision for typical continuous-tone imagery a suboptimal resolution/level tradeoff (see FIG. 1).
Error diffusion is fundamentally different from dither in that there is no fixed screen pattern, instead a recursive algorithm is used that attempts causally to correct errors made by representing the continuous input signal by binary values. The two major components are a matrix of fractions that weight past errors and a threshold operator based on the sum of those weighted errors and the current pixel that determines whether to output an "on" or an "off." The best error diffusion techniques are two-dimensional, meaning that the error is fed back from previous lines as well as previous pixels. The error feedback mechanism is usually linear in that the sum error is a linear combination of past errors, but the thresholding is nonlinear making the compound process nonlinear. Approximating thresholding as a signal-dependent gain, it can be shown that for positive error weights the output binary signal will be high-pass in uniform regions thus introducing "blue noise" into the image (see Ulichney, cited above). This "blue noise" spectrum is shown in FIG. 2. As discussed by Ulichney, this "blue noise" is a very favorable feature because the perception of this noise will be reduced by the low-pass filtering of the visual system causing a higher perceived signal-to-noise ratio. Unfortunately, the error weights are indirectly related to this preferred noise characteristic and therefore provide suboptimal control, and for certain signal levels the causal feedback can become visually unstable generating correlated patterns or "worms" that are highly objectionable. The most common solution is modulating the weights randomly which reduces the "worms" but also increases the noise.
It is the object of the present invention to provide a new digital halftoning technique that improves the image quality over the aforementioned techniques for all classes of images of interest to a human observer. The approach is a combination of the minimal visual modulation patterns and the correlated clustered-dot algorithms.